package q138_copyRandomList;


import java.util.HashMap;
import java.util.Map;

public class Solution_1 {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    /**
     * 深拷贝出来一个与原有链表一样的链表
     * 这里通过map来进行实现
     * 首先是遍历一边过后，将所有的节点都加入到map中，并且生成一个val一样的新节点
     * 然后回到bin = 头节点，只需要
     * map.get(bin).next = map.get(bin.next);
     * map.get(bin).random = map.get(bin.random);
     * 就能够获得一个一样的深拷贝
     * @param head
     * @return
     */
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node bin = head;
        while (bin != null) {
            map.put(bin, new Node(bin.val));
            bin = bin.next;
        }

        bin = head;
        while (bin != null){
            map.get(bin).next = map.get(bin.next);
            map.get(bin).random = map.get(bin.random);
            bin = bin.next;
        }

        return map.get(head);

    }
}
